package primary.linkedlist;

import java.util.HashSet;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;

/**
 * @author zhanb
 * @date 2020/5/17
 */
public class test {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5};
        ListNode head = new ListNode(arr);
        System.out.println(reverseList(head));

//        head = removeNthFromEnd(head, 8);
//        System.out.println(head.toString());

    }

    /**
     * 给定一个链表，判断链表中是否有环。
     *
     * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
     */
    public boolean hasCycle(ListNode head) {
        Set<ListNode> nodesSeen = new HashSet<>();
        while (head != null) {
            if (nodesSeen.contains(head)) {
                return true;
            } else {
                nodesSeen.add(head);
            }
            head = head.next;
        }
        return false;

    }

    /**
     * 输入: 1->2
     * 输出: false
     *
     * 输入: 1->2->2->1
     * 输出: true
     * 请判断一个链表是否为回文链表。
     * @param head
     * @return
     */
    public boolean isPalindrome(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        if(fast != null) {
            slow = slow.next;
        }

        ListNode pre = null;
        while(slow != null) {
            ListNode temp = slow.next;
            slow.next = pre;
            pre = slow;
            slow = temp;
        }

        while(head != null && pre != null) {
            if(head.val != pre.val) {
                return false;
            }
            head = head.next;
            pre = pre.next;
        }
        return true;

    }

    /**
     * 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null) {
            return l2;
        }
        if(l2==null) {
            return l1;
        }
        ListNode newNode=new ListNode(0);
        ListNode newHeadNode=newNode;
        while(l1!=null && l2!=null){
            if(l1.val>l2.val){
                newNode.next=l2;
                l2=l2.next;
            }else{
                newNode.next=l1;
                l1=l1.next;
            }
            newNode=newNode.next;
        }
        if(l1==null) {
            newNode.next=l2;
        }
        if(l2==null) {
            newNode.next=l1;
        }
        return newHeadNode.next;
    }

    /**
     * 方法一：迭代
     * 假设存在链表 1 → 2 → 3 → Ø，我们想要把它改成 Ø ← 1 ← 2 ← 3。
     *链表反转
     * 在遍历列表时，将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。
     * 在更改引用之前，还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用！
     * @param head
     * @return
     */
    public static ListNode reverseList(ListNode head) {
        //反转链表头节点
        ListNode prev = null;
        //当前链表头节点
        ListNode curr = head;
        //保存链表的下一节点
        ListNode nextTemp =null;
        while (curr != null) {
            nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }


    public static ListNode removeNthFromEnd(ListNode head, int n) {
        //当链表为空或者要删除的节点小于等于0的时候，直接返回head
        if (head == null || n <= 0) {
            return head;
        }
        //建立一个虚拟的表头结点，因为需要删除的节点有可能是头结点，
        // 所以建立虚拟头结点可以不用分是否是头结点两种情况
        ListNode tempHead = new ListNode(0);
        tempHead.next = head;
        ListNode p = tempHead, q = tempHead;
        //p指针比q指针先跑n次
        for (int i = 0; i < n; i++) {
            //如果p为空的时候，说明这个节点的长度不足n，返回head
            if (p == null ) {
                return head;
            } else {
                p = p.next;
            }
        }
        //p，q一起往前跑，直到p的next为空，
        // q所指向的下一个结点就是要删除的元素的位置
        while (p.next != null) {
            p = p.next;
            q = q.next;
        }
        //删除q指向的节点的下一个元素
        q.next = q.next.next;
        //删除虚拟头结点
        return tempHead.next;
    }

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
        }

        public ListNode(int[] arr) {
            if (arr == null || arr.length == 0) {
                throw new IllegalArgumentException("arr can to be empty");
            }
            this.val = arr[0];
            ListNode cur = this;
            for (int i = 1; i < arr.length; i++) {
                cur.next = new ListNode(arr[i]);
                cur = cur.next;
            }
        }

        @Override
        public String toString() {
            StringBuilder res = new StringBuilder();
            ListNode cur = this;
            while (cur != null) {
                res.append(cur.val + "->");
                cur = cur.next;
            }
            res.append("NULL");
            return res.toString();
        }
    }
}
